{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>gcForest Algorithm</h1>\n",
    "\n",
    "<p>The gcForest algorithm was suggested in Zhou and Feng 2017 ( https://arxiv.org/abs/1702.08835 , refer for this paper for technical details) and I provide here a python3 implementation of this algorithm.<br>\n",
    "I chose to adopt the scikit-learn syntax for ease of use and hereafter I present how it can be used.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from GCForest import gcForest\n",
    "from sklearn.datasets import load_iris, load_digits\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Before starting, a word about sizes.</h2>\n",
    "<p>*Note* : I recommend the reader to look at this section with the original paper next to the computer to see what I am talking about.</p>\n",
    "<p>The main technical problem in the present gcForest implementation so far is the memory usage when slicing the input data.\n",
    "A naive calculation can actually give you an idea of the number and sizes of objects the algorithm will be dealing with.</p>\n",
    "<p>Starting with a dataset of $N$ samples of size $[l,L]$ and with $C$ classes, the initial \"size\" is:<br><br>\n",
    "$S_{D} = N.l.L$</p>\n",
    "<p>**Slicing Step**<br>\n",
    "If my window is of size $[w_l,w_L]$ and the chosen stride are $[s_l,s_L]$ then the number of slices per sample is :<br>\n",
    "<br>\n",
    "$n_{slices} = \\left(\\frac{l-w_l}{s_l}+1\\right)\\left(\\frac{L-w_L}{s_L}+1\\right)$<br><br>\n",
    "Obviously the size of slice is $w_l.w_L$ hence the total size of the sliced data set is :<br><br>\n",
    "$S_{sliced} = N.w_l.w_L.\\left(\\frac{l-w_l}{s_l}+1\\right)\\left(\\frac{L-w_L}{s_L}+1\\right)$<br>\n",
    "This is when the memory consumption is its peak maximum.</p>\n",
    "<p>**Class Vector after Multi-Grain Scanning**<br>\n",
    "Now all slices are fed to the random forest to generate *class vectors*.\n",
    "The number of class vector per random forest per window per sample is simply equal to the number of slices given to the random forest $n_{cv}(w) = n_{slices}(w)$.\n",
    "Hence, if we have $N_{RF}$ random forest per window the size of a class vector is (recall we have $N$ samples and $C$ classes):<br><br>\n",
    "$S_{cv}(w) = N.n_{cv}(w).N_{RF}.C$<br><br>\n",
    "And finally the total size of the Multi-Grain Scanning output will be:<br><br>\n",
    "$S_{mgs} = N.\\sum_{w} N_{RF}.C.n_{cv}(w)$\n",
    "</p>\n",
    "<p>This short calculation is just meant to give you an idea of the data processing during the Multi-Grain Scanning phase. The actual memory consumption depends on the format given (aka float, int, double, etc.) and it might be worth looking at it carefully when dealing with large datasets.</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Iris example</h2>\n",
    "\n",
    "<p>The iris data set is actually not a very good example as the gcForest algorithm is better suited for time series and images where informations can be found at different scales in one sample.<br>\n",
    "Nonetheless it is still an easy way to test the method.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# loading the data\n",
    "iris = load_iris()\n",
    "X = iris.data\n",
    "y = iris.target\n",
    "X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.33)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>First calling and training the algorithm.\n",
    "A specificity here is the presence of the 'shape_1X' keyword to specify the shape of a single sample.\n",
    "I have added it as pictures fed to the machinery might not be square.<br>\n",
    "Obviously it is not very relevant for the iris data set but still, it has to be defined.</p>\n",
    "<p>**New in version 0.1.3** : possibility to directly use an int as shape_1X for sequence data.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Sequence...\n",
      "Training MGS Random Forests...\n",
      "Adding/Training Layer, n_layer=1\n",
      "Layer validation accuracy = 1.0\n",
      "Adding/Training Layer, n_layer=2\n",
      "Layer validation accuracy = 1.0\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(shape_1X=4, window=2, tolerance=0.0)\n",
    "gcf.fit(X_tr, y_tr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>Now checking the prediction for the test set:<p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Sequence...\n",
      "[0 1 0 2 1 2 1 0 0 1 0 2 2 2 2 2 1 0 1 0 2 2 2 0 0 0 0 2 0 2 0 0 2 0 1 0 0\n",
      " 1 1 2 2 1 2 1 0 0 2 1 0 2]\n"
     ]
    }
   ],
   "source": [
    "pred_X = gcf.predict(X_te)\n",
    "print(pred_X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gcForest accuracy : 0.96\n"
     ]
    }
   ],
   "source": [
    "# evaluating accuracy\n",
    "accuracy = accuracy_score(y_true=y_te, y_pred=pred_X)\n",
    "print('gcForest accuracy : {}'.format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Digits Example</h2>\n",
    "<p>A much better example is the digits data set containing images of hand written digits.\n",
    "The scikit data set can be viewed as a mini-MNIST for training purpose.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# loading the data\n",
    "digits = load_digits()\n",
    "X = digits.data\n",
    "y = digits.target\n",
    "X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> ... taining gcForest ... (can take some time...) </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Images...\n",
      "Training MGS Random Forests...\n",
      "Slicing Images...\n",
      "Training MGS Random Forests...\n",
      "Adding/Training Layer, n_layer=1\n",
      "Layer validation accuracy = 0.9861111111111112\n",
      "Adding/Training Layer, n_layer=2\n",
      "Layer validation accuracy = 0.9861111111111112\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(shape_1X=[8,8], window=[4,6], tolerance=0.0, min_samples_mgs=10, min_samples_cascade=7)\n",
    "gcf.fit(X_tr, y_tr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p> ... and predicting classes ... </p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Images...\n",
      "Slicing Images...\n",
      "[0 1 0 2 4 3 7 1 4 6 9 5 5 2 6 4 7 7 5 2 1 6 8 6 4 3 3 3 0 9 3 7 3 4 5 2 5\n",
      " 4 2 1 3 6 9 8 5 8 6 2 2 7 8 6 0 3 0 9 5 0 4 6 7 0 3 8 0 6 9 1 8 3 9 1 1 3\n",
      " 7 3 5 6 6 6 9 4 0 8 7 3 0 0 4 2 7 0 4 7 9 7 9 6 4 4 7 0 2 2 5 9 4 5 7 7 7\n",
      " 7 0 6 0 1 6 3 9 4 7 3 1 1 3 6 3 0 3 8 8 1 9 7 6 4 7 5 5 3 5 4 8 3 4 4 6 4\n",
      " 0 5 9 6 8 5 1 3 1 9 9 5 4 0 4 1 1 7 9 2 3 5 5 6 5 4 6 3 7 5 1 9 6 8 1 7 4\n",
      " 9 7 3 0 7 3 6 5 9 7 7 9 7 2 3 8 8 7 7 9 4 5 9 0 7 6 1 4 5 7 6 6 0 4 5 9 3\n",
      " 6 4 0 6 4 6 4 9 1 3 7 3 4 8 8 0 7 4 1 5 5 8 2 0 7 7 6 4 5 8 1 2 0 4 5 7 4\n",
      " 8 5 4 5 8 3 5 9 6 2 7 6 7 1 3 4 1 0 6 9 4 0 7 6 0 0 9 2 7 4 3 9 3 9 0 4 1\n",
      " 0 2 9 0 9 0 6 2 4 0 1 6 9 0 2 0 9 1 1 5 3 4 2 9 6 1 6 1 3 9 1 1 8 6 4 9 3\n",
      " 5 5 2 1 4 8 8 2 2 9 0 9 4 4 2 0 6 2 6 1 7 4 6 7 7 1 5 6 9 7 2 6 0 5 8 7 5\n",
      " 8 4 2 6 9 2 5 6 5 7 4 3 1 2 7 9 5 3 0 2 6 9 9 1 6 0 9 4 5 7 8 4 8 9 6 5 6\n",
      " 6 2 1 4 3 3 5 8 2 0 6 5 9 8 7 4 8 6 1 0 1 8 4 3 9 4 5 5 7 9 8 6 1 7 0 8 2\n",
      " 5 2 5 9 8 4 0 8 7 3 9 7 4 5 5 3 7 4 7 6 0 8 0 9 5 6 0 3 1 6 7 6 4 6 4 7 6\n",
      " 0 0 6 7 7 2 2 9 8 9 8 8 5 5 4 1 4 6 3 8 8 0 0 1 4 4 7 3 3 4 7 1 3 3 9 2 4\n",
      " 0 9 4 9 1 5 1 4 4 5 8 5 7 6 8 8 0 8 1 4 6 0 2 0 1 6 0 3 0 8 1 2 3 2 5 0 4\n",
      " 0 2 1 9 2 3 2 6 3 9 9 2 6 8 3 0 8 0 5 8 4 2 2 4 6 5 7 1 2 6 9 1 2 8 8 7 5\n",
      " 9 1 5 0 2 2 5 6 7 0 7 3 5 5 2 2 7 1 1 7 0 3 7 4 2 1 3 2 9 1 7 4 6 3 1 3 2\n",
      " 7 6 9 2 0 4 6 3 0 7 1 8 4 6 0 7 3 6 3 0 6 3 1 1 5 0 8 9 2 3 0 5 5 3 9 0 9\n",
      " 9 8 6 8 7 8 8 3 1 6 1 4 2 6 0 4 1 4 3 2 1 4 8 8 2 3 3 2 3 9 4 5 3 7 4 2 2\n",
      " 9 2 8 0 9 3 9 3 2 7 1 6 0 7 0 8]\n"
     ]
    }
   ],
   "source": [
    "pred_X = gcf.predict(X_te)\n",
    "print(pred_X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gcForest accuracy : 0.9847009735744089\n"
     ]
    }
   ],
   "source": [
    "# evaluating accuracy\n",
    "accuracy = accuracy_score(y_true=y_te, y_pred=pred_X)\n",
    "print('gcForest accuracy : {}'.format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Saving Models to Disk</h2>\n",
    "<p>You probably don't want to re-train your classifier every day especially if you're using it on large data sets.\n",
    "Fortunately there is a very easy way to save and load models to disk using ```sklearn.externals.joblib```</p>\n",
    "<p>__Saving model:__</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['gcf_model.sav']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.externals import joblib\n",
    "joblib.dump(gcf, 'gcf_model.sav')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>__Loading model__:</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gcf = joblib.load('gcf_model.sav')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Using mg-scanning and cascade_forest Sperately</h2>\n",
    "<p>As the Multi-Grain scanning and the cascade forest modules are quite independent it is possible to use them seperately.<br>\n",
    "If a target `y` is given the code automaticcaly use it for training otherwise it recalls the last trained Random Forests to slice the data.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Images...\n",
      "Training MGS Random Forests...\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(shape_1X=[8,8], window=5, min_samples_mgs=10, min_samples_cascade=7)\n",
    "X_tr_mgs = gcf.mg_scanning(X_tr, y_tr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Slicing Images...\n"
     ]
    }
   ],
   "source": [
    "X_te_mgs = gcf.mg_scanning(X_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p>It is now possible to use the mg_scanning output as input for cascade forests using different parameters. Note that the cascade forest module does not directly return predictions but probability predictions from each Random Forest in the last layer of the cascade. Hence the need to first take the mean of the output and then find the max.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding/Training Layer, n_layer=1\n",
      "Layer validation accuracy = 0.9814814814814815\n",
      "Adding/Training Layer, n_layer=2\n",
      "Layer validation accuracy = 0.9814814814814815\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(tolerance=0.0, min_samples_mgs=10, min_samples_cascade=7)\n",
    "_ = gcf.cascade_forest(X_tr_mgs, y_tr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.97635605006954107"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pred_proba = gcf.cascade_forest(X_te_mgs)\n",
    "tmp = np.mean(pred_proba, axis=0)\n",
    "preds = np.argmax(tmp, axis=1)\n",
    "accuracy_score(y_true=y_te, y_pred=preds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding/Training Layer, n_layer=1\n",
      "Layer validation accuracy = 0.9675925925925926\n",
      "Adding/Training Layer, n_layer=2\n",
      "Layer validation accuracy = 0.9722222222222222\n",
      "Adding/Training Layer, n_layer=3\n",
      "Layer validation accuracy = 0.9722222222222222\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(tolerance=0.0, min_samples_mgs=20, min_samples_cascade=10)\n",
    "_ = gcf.cascade_forest(X_tr_mgs, y_tr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.97635605006954107"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pred_proba = gcf.cascade_forest(X_te_mgs)\n",
    "tmp = np.mean(pred_proba, axis=0)\n",
    "preds = np.argmax(tmp, axis=1)\n",
    "accuracy_score(y_true=y_te, y_pred=preds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<h3>Skipping mg_scanning</h3>\n",
    "<p>It is also possible to directly use the cascade forest and skip the multi grain scanning step.</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding/Training Layer, n_layer=1\n",
      "Layer validation accuracy = 0.9583333333333334\n",
      "Adding/Training Layer, n_layer=2\n",
      "Layer validation accuracy = 0.9583333333333334\n"
     ]
    }
   ],
   "source": [
    "gcf = gcForest(tolerance=0.0, min_samples_cascade=20)\n",
    "_ = gcf.cascade_forest(X_tr, y_tr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.95827538247566069"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pred_proba = gcf.cascade_forest(X_te)\n",
    "tmp = np.mean(pred_proba, axis=0)\n",
    "preds = np.argmax(tmp, axis=1)\n",
    "accuracy_score(y_true=y_te, y_pred=preds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
